package code;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

public class Code211 {
	
	/*
	 * 定义字典树
	 */
	public class DicNode{
		int val;
		boolean isWord;
		DicNode[] children;
		public DicNode(int x){
			val=x;
			isWord=false;
			children=new DicNode[26];
			for(int i=0;i<26;i++)
				children[i]=null;
		}
	}
	
	/*
	 * 初始化,根节点
	 */
	private DicNode root=new DicNode(0);
	
    public void addWord(String word) {
    	int i;
    	int len=word.length();
    	DicNode p=root;
    	for(i=0;i<len;i++){
    		int off=word.charAt(i)-'a';
    		/*
    		 * 节点不存在，那么新建一个节点
    		 */
    		if(p.children[off]==null){
    			DicNode node=new DicNode(off);
    			p.children[off]=node;
    		}
    		p=p.children[off];
    	}
    	/*
    	 * 再将最后的p标记为叶子节点，表示这是一个单词的结尾
    	 */
    	p.isWord=true;
    }

    public boolean find(DicNode p,String word,int idx){
    	
    	if(p==null)
    		return false;
    	if(idx==word.length()){
    		return p.isWord;
    	}
    	if(word.charAt(idx)=='.'){
    		for(int i=0;i<26;i++){
    			if(find(p.children[i],word,idx+1))
    				return true;
    		}
    	}
    	else{
        	int off=word.charAt(idx)-'a';
        	return find(p.children[off],word,idx+1);
    	}
    	return false;
    }
    public boolean search(String word) {
        return find(root,word,0);
    }
    
    public static void main(String[] args){
    	Code211 code211=new Code211();
//    	code211.addWord("a");
//    	code211.addWord("ab");
    	System.out.println(code211.search("a"));
    }
}
